#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>

using namespace std;

struct ListNode 
{
	int val;
	struct ListNode* next;
	ListNode(int x) : val(x), next(nullptr) {}
};

int ListSize(ListNode* phead)
{
	int size = 0;
	ListNode* cur = phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

void _MergeSort(int* arr, int left, int right, int* temp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, temp);
	_MergeSort(arr, mid + 1, right, temp);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[index++] = arr[begin1++];
		}
		else
		{
			temp[index++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[index++] = arr[begin2++];
	}
	for (int i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

void MergeSort(int* arr, int n)
{
	int* temp = new int[n];
	_MergeSort(arr, 0, n - 1, temp);
	delete[] temp;
}

void ListPushBack(ListNode** pphead, int x)
{
	ListNode* new_node = new ListNode(x);
	if (*pphead == nullptr)
	{
		*pphead = new_node;
	}
	else
	{
		ListNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = new_node;
	}
}

ListNode* sortInList(ListNode* head)
{
	int size = ListSize(head);
	int* arr = new int[size];
	ListNode* cur = head;
	for (int i = 0; i < size; i++)
	{
		arr[i] = cur->val;
		cur = cur->next;
	}
	MergeSort(arr, size);
	ListNode* plist = nullptr;
	cur = head;
	for (int i = 0; i < size; i++)
	{
		cur->val = arr[i];
		cur = cur->next;
	}
	return head;
}

void Print(ListNode* phead)
{
	ListNode* cur = phead;
	while (cur)
	{
		cout << cur->val << ' ';
		cur = cur->next;
	}
	cout << endl;
}

int main()
{
	int arr[] = { -426572,-406609,724427,-157789,-132713,720732,-39078,-348926,-693458,559374,114739,-748249,428207,-767407,
		401563,646432,-682870,483610,-608888,94840,749542,359115,131739,935294,347325,80573,-869091,-757897,-860166,-227942,
		-484068,-170790,-362441,-860466,819197,817675,886101,463504,-100482,496406,-860791 };
	ListNode* head = nullptr;
	int size = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < size; i++)
	{
		ListPushBack(&head, arr[i]);
	}
	head = sortInList(head);
	Print(head);

	return 0;
}